package DoubleLinkedList;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class DoubleLinkedList implements Iterable<Integer> {
	
	private class Node {
		private int element;
		private Node previous;
		private Node next;

		private Node(int element, Node previous, Node next) {
			this.element = element;
			this.previous = previous;
			this.next = next;
		}
		
		private Node(int element, Node previous) {
			this(element, previous, null);
		}
		
		private Node(int element) {
			this(element, null, null);
		}
	}

	private Node head;
	private Node tail;
	private int size;

	public DoubleLinkedList(int[] elements) {
		this();
		for (int i : elements) {
			this.addLast(i);
		}
	}

	public DoubleLinkedList() {
		head = new Node(-1, null);
		tail = new Node(-1, head, null);
		head.next = tail;
	}

	public void addFirst(int element) {
		Node newNode = new Node(element, head, head.next);
		head.next.previous = newNode;
		head.next = newNode;
		size++;
	}
	
	public void addLast(int element) {
		Node newNode = new Node(element, tail.previous, tail);
		tail.previous.next = newNode;
		tail.previous = newNode;
		size++;
	}
	
	public void insert(int element, int position) throws IndexOutOfBoundsException {
		if (position > size) throw new IndexOutOfBoundsException();
		Node current = head.next;
		for(int i = 0; i < position; i++) {
			current = current.next;
		}
		Node newNode = new Node(element, current.previous, current);
		current.previous.next = newNode;
		current.previous = newNode;
		size++;
	}

	public void removeFirst() throws NoSuchElementException {
		if (head.next == tail) throw new NoSuchElementException();
		head.next.next.previous = head;
		head.next = head.next.next;
		size--;
	}
	
	public void removeLast() {
		if (tail.previous == head) throw new NoSuchElementException();
		tail.previous.previous.next = tail;
		tail.previous = tail.previous.previous;
		size--;
	}
	
	public boolean remove(int element) {
		Node current = head.next;
		while (current != tail) {
			if (current.element == element) {
				current.previous.next = current.next;
				current.next.previous = current.previous;
				size--;
				return true;
			}
			current = current.next;
		}
		return false;
	}

	public boolean contains(int element) {
		Node current = head;
		while (current != tail) {
			if (current.element == element)
				return true;
			current = current.next;
		}
		return false;
	}

	public int size() {
		return size;
	}

	public void clear() {
		head = new Node(-1, null);
		tail = new Node(-1, head, null);
		head.next = tail;
		size = 0;
	}

	public int indexOf(int element) {
		Node current = head.next;
		int index = 0;
		while (current != tail) {
			if (current.element == element)
				return index;
			index++;
			current = current.next;
		}
		return -1;
	}
	
	@Override
	public Iterator<Integer> iterator() {
		Iterator<Integer> iterator = new Iterator<Integer>() {
			
			private Node current = head;
			
			@Override
			public void remove() {
				//DoubleLinkedList.this.remove(current.element);
			}
			
			@Override
			public Integer next() {
				current = current.next;
				return current.element;
			}
			
			@Override
			public boolean hasNext() {
				if (current.next != tail) return true;
				return false;
			}
		};
		return iterator;
	}
	
	public Iterator<Integer> descendingIterator() {
		Iterator<Integer> iterator = new Iterator<Integer>() {
			
			private Node current = tail;
			
			@Override
			public void remove() {
				//DoubleLinkedList.this.remove(current.element);
			}
			
			@Override
			public Integer next() {
				current = current.previous;
				return current.element;
			}
			
			@Override
			public boolean hasNext() {
				if (current.previous != head) return true;
				return false;
			}
		};
		return iterator;
	}
	
	public int[] toArray() {
		int[] array = new int[size];
		Node current = head.next;
		int index = 0;
		while (current != tail) {
			array[index] = current.element;
			index++;
			current = current.next;
		}
		return array;
	}

	@Override
	public String toString() {
		Node current = head.next;
		StringBuilder s = new StringBuilder();
		while (current != tail) {
			s.append(current.element);
			s.append(' ');
			current = current.next;
		}
		return s.toString().trim();
	}
}
